// https://leetcode-cn.com/problems/find-all-numbers-disappeared-in-an-array/submissions/

class Solution {
public:
    // 法一：额外开辟map
    // vector<int> findDisappearedNumbers(vector<int>& nums) {
    //     int n = nums.size();
    //     vector<int> rec(n + 1, 0);
    //     vector<int> res;
    //     for (int i = 0; i < n; ++i) {
    //         rec[nums[i]] = 1;
    //     }
    //     for (int i = 1; i < rec.size(); ++i) {
    //         if (!rec[i]) res.push_back(i);
    //     }
    //     return res;
    // }

    // 法二：利用nums本身作记录
    vector<int> findDisappearedNumbers(vector<int>& nums) {
        int n = nums.size();
        vector<int> res;
        // for (int i = 0; i < n; ++i) {
        //     if (nums[i] != i + 1 && nums[nums[i] - 1] != nums[i])
        //         swap(nums[i], nums[nums[i] - 1];

        // }
        int i = 0;
        while (i < n) {
            if (nums[i] == i + 1 || nums[nums[i] - 1] == nums[i]) {
                i++;
                continue;
            } 
            swap(nums[i], nums[nums[i] - 1]);
        }
        for (int i = 0; i < nums.size(); ++i) {
            if (nums[i] != i + 1) 
                // res.push_back(nums[i]);
                res.push_back(i + 1);
        }
        return res;
    }
};